package main.leetcode.offer.firstround.from51to68;

/**
 * 56-II.数组中数字出现的次数II
 *
 * <p>在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
 *
 * <p>
 *
 * <p>示例 1：输入：nums = [3,4,3,3] 输出：4
 *
 * <p>示例 2：输入：nums = [9,1,7,9,7,9,7] 输出：1
 *
 * <p>限制：1 <= nums.length <= 10000 1 <= nums[i] < 2^31
 *
 * <p>来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex56II {
    public static void main(String[] args) {
        System.out.println(new ex56II().singleNumber(new int[] {3, 4, 3, 3}));
    }

    public int singleNumber(int[] nums) {
        if (nums.length == 1) return nums[0];
        int res = 0, count, tmp = 1;
        for (int i = 0; i < 32; i++) {
            count = 0;
            for (int val : nums) {
                if ((val & tmp) != 0) ++count;
            }
            if (count % 3 != 0) res |= 1 << i;
            tmp <<= 1;
        }
        return res;
    }
}
